/**
 * 剑指 Offer 68 - II. 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
 */
const { createTreeNode } = require('../../libs/public');

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {number} depth
 * @return {TreeNode[]}
 */
function search(root, p, depth) {
  if (!root) {
    return null;
  }
  if (root === p) {
    const result = new Array(depth + 1);
    result[depth] = root;
    return result;
  }
  const leftResult = search(root.left, p, depth + 1);
  if (leftResult) {
    leftResult[depth] = root;
    return leftResult;
  }
  const rightResult = search(root.right, p, depth + 1);
  if (rightResult) {
    rightResult[depth] = root;
    return rightResult;
  }
  return null;
}

/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
function lowestCommonAncestor(root, p, q) {
  const pParents = search(root, p, 0);
  const qParents = search(root, q, 0);
  let index = 0;
  while (pParents[index + 1] === qParents[index + 1]) {
    index += 1;
  }
  return pParents[index];
}

let root;

root = createTreeNode([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
console.log(lowestCommonAncestor(root, root.left, root.right) === root);
root = createTreeNode([6, 2, 8, 0, 4, 7, 9, null, null, 3, 5]);
console.log(lowestCommonAncestor(root, root.left, root.left.right) === root.left);
